package arithmetic2.day04;

import java.util.Arrays;

/*
    将链表中小于某个值的数放在链表左边，等于的放在中间，大于的放在右边
 */
public class Demo05 {
    public static void main(String[] args) {
        MyList list = new MyList();
        list.tailAdd(5);
        list.tailAdd(2);
        list.tailAdd(1);
        list.tailAdd(6);
        list.tailAdd(4);
        list.print();
//        partition1(list,4);
        partition2(list,5);
        list.print();
    }

    //一般方法
    public static void partition1(MyList list,int key) {
        //将链表中所有数据取出来放到数组中
        int values[] = list.toArray();
        //将数组划分
        partitionArr(values,key);
        //将链表清空，重新赋值
        list.clear();
        for(int value:values){
            list.tailAdd(value);
        }
    }

    //采用6个变量的方法
    public static void partition2(MyList list,int key){
        list.partition(key);
    }

    //划分算法，将数组中小于key的数放在数组左边，等于key的数放在数组中间，大于key的数放在数组右边
    public static void partitionArr(int arr[],int key){
        int i = -1;  //小于等区域的最大索引,左边索引的数都是小于key的
        int j = arr.length; //大于区域的最小索引，右边的数都是大于key的
        //遍历当前数组
        for(int k=0;k<arr.length && j>k;k++){
            if(arr[k]<key){    //当前数<key，将当前数与小于等于区域的下一个数交换，小于区域右扩1个 k++
                swap(arr,k,i+1);
                i++;
            }else if(arr[k]>key){  //当前数>key 将当前数与大于区的前一个数交换，大于区左扩,k不变
                swap(arr,k,j-1);
                j--;
                k--;
            }
        }
    }

    //交换两个数
    public static void swap(int arr[],int i,int j){
        int temp =  arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
